#pragma once

#include <algorithm>
#include <vector>

namespace solution_056
{

class Solution
{
public:
    std::vector< std::vector<int> > merge(
            std::vector< std::vector<int> >& intervals)
    {
        std::sort(intervals.begin(), intervals.end(),
                  [](auto& lhs, auto& rhs) { return lhs.front() < rhs.front(); });
        
        std::vector< std::vector<int> > merged{ std::move(intervals.front()) };
        for (size_t i = 1; i < intervals.size(); ++i) {
            auto& interval = intervals.at(i);
            if (interval.front() <= merged.back().back())
                merged.back().back() = std::max(merged.back().back(), interval.back());
            else
                merged.push_back(std::move(interval));
        }
        return merged;
    }
};

}  /* namespace solution_056 */
